import java.util.ArrayList;
import java.util.List;

public class Test01 {

    public static void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {
        //第一步
        //把 a 上面所有的盘子 借助 b 放到 c 上面
        //我相信 dfs函数 能帮我解决
        dfs(a,b,c, a.size());
    }

    private static void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {
        //处理边界情况
        if (n == 1){
            c.add(a.remove(a.size() - 1));
            return;
        }
        //函数体的主逻辑
        //将 a 上 n - 1 个盘子 借助 c 挪到 b 上
        dfs(a,c,b, n - 1);
        //将 a 上剩余的最后一个盘子挪到 c 上
        c.add(a.remove(a.size() - 1));
        //将 b 上面 n - 1 个盘子借助 a 挪到 c 上面
        dfs(b,a,c,n - 1);
    }

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>();
        a.add(2);
        a.add(1);
        a.add(0);
        List<Integer> b = new ArrayList<>();
        b.add(0);
        List<Integer> c = new ArrayList<>();
        c.add(0);
        hanota(a,b,c);
    }
}
